1. Field of the Invention
This invention relates to the field of data processing systems. More particularly, this invention relates to pipelined data processing systems including branch prediction mechanisms.
2. Description of the Prior Art
It is known to provide pipelined data processing systems including a sequence of pipelined stages respectively performing different parts of the overall execution of program instructions as they progress through the different pipeline stages. Within such pipelined systems, program instructions are fetched and start to progress along the pipeline before those instructions preceding them in the pipeline have completed their execution. This results in a problem in the case of conditional branch instructions since it is not determined until those instructions have reached a relatively late stage within the pipeline whether or not the branch will be taken or not taken. Accordingly, the sequence of program instructions to be fetched into the pipeline following the conditional branch instruction can change.
In order to deal with this problem it is known to provide branch prediction mechanisms which seek to predict whether or not a particular conditional branch instruction will be taken. The consequences of misprediction are relatively severe as it is then necessary to flush the pipeline, reload the corrected sequence of program instructions and restart execution at the cost of many processor cycles. Accordingly, sophisticated and often multiple branch prediction mechanisms may be included within high performance systems with the aim of increasing branch prediction accuracy.
One known form of branch prediction mechanism learns patterns of branch behavior; using a history of recent branch outcomes to predict what will happen next. For this type of branch prediction mechanism it is known to store multiple prediction levels associated with each branch to be predicted indicating, for example, whether that branch is predicted as strongly taken, weakly taken, weakly not taken or strongly not taken. This form of prediction storage provides a degree of hysteresis in the prediction thereby preventing the predictions from being too rapidly perturbed by relatively infrequent mispredictions. A disadvantage of storing such multiple levels of prediction for each branch is the associated circuit area, power consumption, complexity etc. A second disadvantage is that the hysteresis increases the time it takes the predictor to learn a new pattern of branch behavior, on a task switch for example.
It is desirable to provide branch prediction mechanisms with a high degree of accuracy and yet which add a relatively low level of additional circuit overhead. This is particularly the case in the context of embedded systems in which overhead in terms of circuit area and power consumption is critical.